package divideandconquer;

import org.junit.Test;
import sort.Example;

/**
 * @author DuJiabao
 * @create 2021-01-02 13:00
 */
public class ReverseOrderPair extends Example {
    private static int num = 0; // 保存逆序的个数

    private static int count(Comparable[] array) {
        num = 0;
        mergeSort(array, 0, array.length);
        return num;
    }

    /**
     * 左闭右开区间
     *
     * @param array
     * @param start
     * @param end
     */
    private static void mergeSort(Comparable[] array, int start, int end) {
        if (end - start <= 1) return;
        int middle = (end + start) / 2;
        mergeSort(array, start, middle);
        mergeSort(array, middle, end);
        merge(array, start, middle, end);
    }

    /**
     * 左闭右开区间
     *
     * @param array
     * @param start
     * @param middle
     * @param end
     */
    private static void merge(Comparable[] array, int start, int middle, int end) {
        Comparable[] temp = new Comparable[end - start];  // 临时存放的地方
        int p1 = start;
        int p2 = middle;
        int p3 = 0;
        while (p1 < middle && p2 < end) {
            if (less(array[p2], array[p1])) {
                temp[p3++] = array[p2++];
                num += middle - p1;  //计算还有多少个没有merge，就是那些比它大的，也就是逆序。也就是说，剩下多少个，也就是反逆序了多少个了！
            } else {
                temp[p3++] = array[p1++];
            }
        }
        // 剩下的
        while (p1 < middle) {
            temp[p3++] = array[p1++];
        }
        // 剩下的
        while (p2 < end) {
            temp[p3++] = array[p2++];
        }
        //把它复制回去
        p1 = start;
        for (Comparable comparable : temp) {
            array[p1++] = comparable;
        }
    }

    @Test
    public void test() {
        Integer[] arr = new Integer[]{1, 2, 3, 4, 1, 2, 3};
        System.out.println(count(arr));
    }
}
